package com.example.leetcode.tree;


/**
 * 对称二叉树
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 *
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 *
 * 思路：递归
 * 如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
 *
 */
public class IsSymmetric {

    public boolean isSymmetric(TreeNode root) {
        // 判断当前节点的左子树和右子树是否对称
        return check2(root.left, root.right);
    }

    private boolean check2(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        return p.val == q.val && check2(p.left, q.right) && check2(p.right, q.left);
    }






















    public boolean check(TreeNode p, TreeNode q) {
        // 当左子树和右子树都为null,对称
        if (p == null && q == null) {
            return true;
        }
        // 只有一个为null, 不对称
        if (p == null || q == null) {
            return false;
        }
        // 左子树和右子树值相等 并且 根节点p的左子树和根节点q的右子树对称 并且 根节点p的右子树和根节点q的左子树对称
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }


}
